package 每日一题.买卖股票的最佳时机;

/**
 * @author 标记
 * @date 2021/1/29
 */
public class test {

    public static void main(String[] args) {
        int[] a = {15,3,7,8};
        int i = maxProfitViolence(a);
        System.out.println(i);

        System.out.println("------------------------");

    }

    /**
     * 股票买卖（只能进行一次买入和卖出），求最大收益
     * 暴力解法
     * 【例子】:[7,1,5,3,6,4]
     * @param prices
     * @return
     */
    public static int maxProfitViolence(int[] prices) {
        int maxResult = 0;

        for (int i = 0; i < prices.length ; i++) {
            for (int j = i+1; j < prices.length ; j++) {
                //maxResult = prices[j]-prices[i]>maxResult?prices[j]-prices[i]:maxResult;
                maxResult = Math.max(prices[j] - prices[i], maxResult);
            }
        }
        return maxResult;
    }

    /**
     * 买卖股票的最佳时机：只能买卖一次
     * 		动态规划解决
     * 【例子】:[7,1,5,3,6,4]
     *
     *  解题思路：
     *  s1: 记录今天之前买入的最小值
     *  s2: 计算今天卖出的最大获利
     *  s3: 比较每天的最大获利
     *
     * @param prices
     * @return
     */
    public static int maxProfitDynamic(int[] prices) {

        if (prices.length <= 1) {
            return 0;
        }

        int maxProfit = 0;
        int minNum = prices[0];
        for (int i = 0; i < prices.length ; i++) {
            maxProfit = Math.max(prices[i] - minNum, maxProfit);
            minNum = Math.min(minNum,prices[i]);
        }

        return maxProfit;
    }


}
